0% completed
In this lesson, we will cover three fundamental graph algorithms:
- Breadth-First Search (BFS)
- Depth-First Search (DFS)
- Dijkstra's Algorithm
Each algorithm will be explained with Java code and detailed complexity analysis.
1. Breadth-First Search (BFS)
BFS is a traversal algorithm that explores the graph level by level, starting from the source node and visiting all its neighbors before moving to the next level.
Time Complexity for BFS Code
-
Initialization:
- Queue Initialization: Initializing the queue is
.
- Queue Initialization: Initializing the queue is
-
Traversal:
- Outer While Loop:
- The loop runs as long as the queue is not empty. Each vertex is enqueued and dequeued exactly once.
- The
poll()operation isand runs times, where Vis the number of vertices.
- Inner For Loop:
- Iterates over all adjacent nodes of
currentNode. The total number of iterations across allforloops (over all vertices) is, where Eis the number of edges. - The
queue.add()operation for adding nodes to the queue isand is performed at most times.
- Iterates over all adjacent nodes of
- Outer While Loop:
Overall Time Complexity:
- The algorithm visits each vertex and each edge exactly once, resulting in:
, where Vis the number of vertices andEis the number of edges in the graph.
Space Complexity for BFS Code
-
Visited Array:
- The
visitedarray requiresspace to store the visited status for each vertex.
- The
-
Queue:
- The maximum number of vertices stored in the queue at any time is
in the worst case (e.g., when all vertices are at a single level in the graph). - Space used by the queue:
.
- The maximum number of vertices stored in the queue at any time is
Overall Space Complexity:
- The space complexity is:
for the visitedarray and queue.
2. Depth-First Search (DFS)
DFS explores as far as possible along each branch before backtracking, making it useful for pathfinding and connected component analysis.
Time Complexity for DFS Code
- Traversal:
- Recursive Calls:
- Each vertex is visited once, marking it as visited and processing its adjacent vertices.
- For each vertex
node, the adjacent vertices are iterated over, resulting in a time complexity proportional to the number of edges,.
- Recursive Call Stack:
- Each recursive call processes one vertex, and the call stack grows based on the depth of the recursion.
- Recursive Calls:
Overall Time Complexity:
- The total time complexity for DFS is:
, where Vis the number of vertices andEis the number of edges in the graph.
Space Complexity for DFS Code
- Visited Array:
- The
visitedarray requiresspace to keep track of whether each vertex has been visited.
- The
- Recursive Call Stack:
- Depth of Recursion:
- For a balanced graph, the maximum depth of the recursion is
. - In the worst case (e.g., a graph that behaves like a linked list), the depth of the recursion could be
.
- For a balanced graph, the maximum depth of the recursion is
- Depth of Recursion:
Overall Space Complexity:
- The space complexity consists of:
for the visitedarray.for the recursion stack in the worst case.
3. Dijkstra's Algorithm
Dijkstra's Algorithm is used to find the shortest paths from a single source node to all other nodes in a weighted graph with non-negative weights.
Time Complexity for Dijkstra's Algorithm Code
-
Initialization:
- Distances Array: Initializing the
distancesarray takes, where Vis the number of vertices. - Priority Queue Initialization: Adding the starting node to the priority queue is
.
- Distances Array: Initializing the
-
While Loop:
- The main loop runs as long as the priority queue is not empty. Each vertex is added to and removed from the priority queue once.
- Priority Queue Operations:
- Polling: Removing an element from the queue takes
. - Adding/Updating: Inserting or updating an element in the queue also takes
.
- Polling: Removing an element from the queue takes
- Number of Priority Queue Operations: Each vertex and its edges are processed once, resulting in
operations. Here, Erepresents the number of edges in the graph.
-
For Loop (Iterating Over Adjacent Nodes):
- Each edge is relaxed at most once. The sum of iterations over all adjacent nodes across the entire graph is
. - Checking and Updating Distances: Each operation for checking and updating distances runs in
, but adding to the queue takes .
- Each edge is relaxed at most once. The sum of iterations over all adjacent nodes across the entire graph is
Overall Time Complexity:
-
The total time complexity is:
This is due to the use of a priority queue and processing each edge and vertex.
Space Complexity for Dijkstra's Algorithm Code
-
Distances Array:
- Requires
space to store the shortest distances for each vertex.
- Requires
-
Priority Queue:
- Can hold up to
elements at most, leading to space in the worst case.
- Can hold up to
Overall Space Complexity:
- The space complexity consists of:
for the distancesarray.for the priority queue.
On this page
- Breadth-First Search (BFS)
Time Complexity for BFS Code
Space Complexity for BFS Code
- Depth-First Search (DFS)
Time Complexity for DFS Code
Space Complexity for DFS Code
- Dijkstra's Algorithm
Time Complexity for Dijkstra's Algorithm Code
Space Complexity for Dijkstra's Algorithm Code